翻訳と辞書 Words near each other ・ Kirchheim unter Teck ・ Kirchheim, Bas-Rhin ・ Kirchheim, Hesse ・ Kirchheim, Lower Franconia ・ Kirchheim, Thuringia ・ Kirchheimbolanden ・ Kirchheimbolanden (Verbandsgemeinde) ・ Kirchhoff ・ Kirchhoff (crater) ・ Kirchhoff equations ・ Kirchhoff integral theorem ・ Kirchhoff's circuit laws ・ Kirchhoff's diffraction formula ・ Kirchhoff's law of thermal radiation ・ Kirchhoff's laws ・ Kirchhoff's theorem ・ Kirchhoff–Love plate theory ・ Kirchhorsten railway station ・ Kirchhundem ・ Kirchilpe ・ Kirchiyaan ・ Kirchlauter ・ Kirchleerau ・ Kirchlengern ・ Kirchlengern station ・ Kirchlespitz ・ Kirchliche Arbeit Alpirsbach ・ Kirchliches Handlexikon ・ Kirchlindach ・ Kirchlinteln Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Kirchhoff's theorem ： ウィキペディア英語版 Kirchhoff's theorem In the mathematical field of graph theory Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time as the determinant of a matrix derived from the graph. It is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph. Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a (0,1)-matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise). For a given connected graph ''G'' with ''n'' labeled vertices, let ''λ''1, ''λ''2, ..., ''λn''−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of ''G'' is :$t(G)=\backslash frac\; \backslash lambda\_1\backslash lambda\_2\backslash cdots\backslash lambda\_\backslash ,.$ Equivalently the number of spanning trees is equal to ''any'' cofactor of the Laplacian matrix of ''G''. == An example using the matrix-tree theorem == First, construct the Laplacian matrix ''Q'' for the example kite graph ''G'' (see image at right): : -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ 0 & -1 & -1 & 2 \end\right ). Next, construct a matrix ''Q *'' by deleting any row and any column from ''Q''. For example, deleting row 1 and column 1 yields : $Q^\backslash ast\; =$ \left(& -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 2 \end\right ). Finally, take the determinant of ''Q *'' to obtain ''t(G)'', which is 8 for the kite graph. (Notice ''t(G)'' is the ''(1,1)''-cofactor of ''Q'' in this example.) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kirchhoff's theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.